AI has a big overlap with the general area of optimization because the search for the desired model is a process of identifying the model that best meets the goal. In some algorithms, such models can be derived analytically. Such deduction can also be counted as optimization because we essentially use the exact optimization methods. Examples include the linear models and support vector machines, which involve the linear least squares method and the Lagrangian multipliers method, respectively. Though many people do not treat these efforts as optimization, most people would agree those gradient descent methods in deep learning, which involve an interactive process for identifying the optimal model, should touch the core of optimization. But no matter how we view this overlap, it seems to be consensed that optimization tools, at least some optimization methods, are an essential part of modern AI predominated by machine learning. In typical optimization problems, we try to maximize or minimize an objective function, $f(\overrightarrow{x})$$f(\overrightarrow{x})$f( vec(x))f(\vec{x})$f(\overrightarrow{x})$, where $\overrightarrow{x}$$\overrightarrow{x}$vec(x)\vec{x}$\overrightarrow{x}$ is a vector of continuous/discrete values.

The classification of optimization methods can be rather diverse, depending on classification criteria including but not limited to the consideration of uncertainty, continuity of the parameters to be optimized, continuity and differentiability of the objective functions, search for global vs. local optima, existence of constraints, and number of objective functions. As mentioned above, optimization methods in machine learning can be roughly classified as exact methods (linear programming, quadratic programming, dynamic programming, branch and bound), general approximate (heuristic) methods (Hill Climbing, Tabu Search, Simulated Annealing, Evolutionary Algorithms (including Genetic Algorithm), Swarming Intelligence Algorithms (Ant Colony, Honeybee Mating, Particle Swarm)), gradient-based methods (first order gradient) (GD, BGD, MBGD, SGD, Nesterov, Momentum, AdaGrad, Adam, AdaDelta, RMSProp), and Newton's and quasi-Newton methods (second order gradient) (including BGFS). The conjugate direction method and its nonlinear variants can be regarded as a hybrid between the gradient-based methods (first-order method that uses the steepest descent gradient) and Newton's method (second-order method that uses Hessian as well). Another major category of optimization methods in AI, Expectation Maximization (EM) algorithms, can be roughly viewed as a category of more general approximate methods.

Exact methods, gradient-based methods, and EM are the three main categories of optimization methods in contemporary AI. In this book, linear least squares, Lagrangian multipliers, and gradient-based methods have been well discussed in the chapters for linear models, SVM, and deep learning. Newton's and quasi-Newton methods gained popularity in deep learning but have not been discussed, so some information will be given in this section. Conjugate gradient methods, which are very useful but have not been that widely adopted in AI, i.e., in deep learning, due to a variety of reasons, will also be discussed considering their wide applicability and possible use in the future of AI. EM has lots of applications in machine learning including Gaussian Mixtures, clustering algorithms, K-means, and HMM, etc., but it has not been systematically discussed in the previous chapters. Thus, EM will also be explained in the following.

Gradient descent is a predominant category of optimization methods in deep learning, thus, a must-know. The basic algorithm is the Batch Gradient Descent (BGD), which uses the gradients of the whole batch (all the training samples) for update. Mini-Batch Gradient Descent (MGBD) is the one that we possibly most frequently use. Here, we draw a portion of samples, i.e., mini batch, from the whole batch and update the model parameters using the gradients calculated with this mini-batch of samples. Thus, this mini-batch actually corresponds to the 'batch' in the parameter 'batch size", which is used in most deep learning software. The use of such mini-batch introduces stochasticity, which sometimes helps jump out of local minimums. Following this direction, we can reach the extreme of introducing the utmost stochasticity: Stochastic Gradient Descent (SGD). SGD uses one sample randomly drawn from the whole batch to compute the gradients for updating the model.

Most of the optimizers that we use in deep learning are variations of MGBD. The Momentum method includes the gradients of the previous update step in addition to the use of the gradients of the current step, which helps the optimizer jump off the local optima or saddle points. The Nesterov or Nesterov momentum uses the gradients at a "future" point for update and thus can be viewed as a modification of the Momentum method. AdaGrad is proposed to automatically adjust the learning rate. AdaDelta is proposed to address three issues with AdaGrad: 1) monotonically decreasing learning rate, which can lead to excessively small learning rates in late training stages, 2) inconsistent units on two sides of the update equation, and 3) the manually set initial learning rate. As a variation and a special case of AdaDelta, RMSprop is between AdaGrad and AdaDelta. Adaptive Moment Estimation (Adam) is essentially RMSprop with momentum and can compute adaptive learning rates. Nadam can be viewed as an Adam variation with Nesterov momentum. More details are available
in the chapter for deep learning.
Gradient-based methods are usually explained using the idea of hill-climbing (in fact, "valley-descending") as we move along the fastest descent direction to move towards the bottom of a valley. Alternatively, we can understand gradientbased methods as a process of approximating the true objective function using an approximate function and then using the minimal point of this approximate function as the next point to move to in an iterative process.

Figure 17.1: Approximation for optimization
As illustrated in Fig. 17.1, we use a function $g_n(x)$$g_n(x)$g_(n)(x)g_{n}(x)$g_n(x)$ to approximate the objective function $f(x)$$f(x)$f(x)f(x)$f(x)$, for which the exact function is unknown yet can be complex. Since we know the approximate function, its minimal value and the corresponding location can be conveniently identified. As we move to the next iterative step, we will use $g_{n+1}(x)$$g_{n+1}(x)$g_(n+1)(x)g_{n+1}(x)$g_{n+1}(x)$ for the approximation. $g_n(x)$$g_n(x)$g_(n)(x)g_{n}(x)$g_n(x)$ and $g_{n+1}(x)$$g_{n+1}(x)$g_(n+1)(x)g_{n+1}(x)$g_{n+1}(x)$ usually have the same mathematical function but include terms embedding local information, e.g., values and gradients at the current step. The approximate function in gradient-based methods is as follows.

This curve depicts a second-order polynomial that is concave upward. So, we can easily identify the minimum, which happens at $g^{\prime }(x)=0$$g^{\prime }(x)=0$g^(')(x)=0g^{\prime}(x)=0$g^{\prime }(x)=0$. This will give us the location for the minimum value:

where $\alpha$$\alpha$alpha\alpha$\alpha$ is the well-known hyper-parameter, learning rate, or learning step size, which is critical to optimization.
Therefore, we can obtain the following equation for update.

In high-order spaces, i.e., $x$$x$xx$x$ has multiple entities (attributes), then this equation becomes the general update equation for gradient-based methods:

The same idea can be used for optimization but with different approximate functions. In the following, we will see that the above equation can be slightly modified by including a second-order gradient to reach Newton's method. In fact, the selection of more general approximate equations that do not necessarily include any gradients or even without an explicit math function could lead to the idea of Expectation Maximization methods to be introduced in the final. The Conjugate Gradient method and its variations, as an intermediate method between gradient-based methods and Newton's method, use an approximate function with an implicit relationship between the $f^{\prime }(x)$$f^{\prime }(x)$f^(')(x)f^{\prime}(x)$f^{\prime }(x)$ and $\alpha$$\alpha$alpha\alpha$\alpha$, which needs to be obtained in an iterative way.

Using the same approximation concept, we adopt the following equation from Taylor's expansion to approximate the objective function:

For this equation, we can obtain the minimum objective function value at the following point:

This will surrender the following equation for update:

Newton's method can help us quickly find a global minimum if $f(x)$$f(x)$f(x)f(x)$f(x)$ is smooth enough. However, the actual objective function is usually much more complicated than that. If the computational demand is not a concern, Newton's method is, in general, much better than gradient-based methods. However, the calculation of the second-order gradients, i.e., the Hessian matrix, could be very computationally expensive. To address this issue, many quasi-Newton methods such as BFGS, SR1 formula, and BHHH have been proposed to approximate the Hessian matrix.

It is worthwhile to mention Newton's method has also been widely used for solving equations. But equation solution and optimization can be correlated. The corresponding problem for the equation solution is $f^{\prime }(x)=0$$f^{\prime }(x)=0$f^(')(x)=0f^{\prime}(x)=0$f^{\prime }(x)=0$. That is, the search for the minimum of $f(x)$$f(x)$f(x)f(x)$f(x)$ is the same problem as solving the equation $f^{\prime }(x)=0$$f^{\prime }(x)=0$f^(')(x)=0f^{\prime}(x)=0$f^{\prime }(x)=0$.

The Conjugate Gradient (CG) approach and its variations have been widely used for solving large-scale linear systems of equations and nonlinear optimization problems. First-order methods like gradient-based methods have a slow convergence speed, while second-order methods like Newton's methods are resource-heavy. Conjugate gradient optimization is an intermediate algorithm, it integrates the advantages of only utilizing first-order information while ensuring the convergence speeds of high-order methods. Similar to gradient-based methods and quasi-Newton methods, methods in the CG family are also among the approximate optimization methods, which use a function to approximate the objective function and search for the optimum using this approximate function. This can be proven, but the deduction is excluded here considering it is not essential in the understanding and use of this type of method.

Compared with gradient-based methods, CG can address one critical question: how to determine the learning step size. In gradient-based methods, such a step size is determined either manually based on experience or automatically using some algorithms. The determination of the step size is critical to the optimization speed and results in many cases and still needs to be carefully handled to ensure acceptable results. Newton's method and quasi-Newton methods use the second-order gradient to address this issue, which offers a more accurate but computationally expensive solution. CG does not need to resort to second-order gradients, thus circumvents the trouble of computing them.

To reach a general deduction, we still resort to the following general equation for update:

CG is mostly used for data spaces with two or more dimensions, i.e., the model coefficient $\overrightarrow{x}$$\overrightarrow{x}$vec(x)\vec{x}$\overrightarrow{x}$ ( $\overrightarrow{\theta }$$\overrightarrow{\theta }$vec(theta)\vec{\theta}$\overrightarrow{\theta }$ in other chapters; please be aware $\overrightarrow{x}$$\overrightarrow{x}$vec(x)\vec{x}$\overrightarrow{x}$ is not a sample here) has two or more parameters. Thus, we use $\overrightarrow{x}$$\overrightarrow{x}$vec(x)\vec{x}$\overrightarrow{x}$ rather than $x$$x$xx$x$ as in those subsections for other optimization methods.

The essence of CG can be understood as follows. Like regular gradient-based methods, CG also moves along the fastest descent direction. Therefore, the step size vector ${\alpha }_i{\overrightarrow{r}}_i$${\alpha }_i{\overrightarrow{r}}_i$alpha_(i) vec(r)_(i)\alpha_{i} \vec{r}_{i}${\alpha }_i{\overrightarrow{r}}_i$ is proportional to the gradients: ${\overrightarrow{r}}_i=-\frac{df\left({\overrightarrow{x}}_i\right)}{d{\overrightarrow{x}}_i}$${\overrightarrow{r}}_i=-\frac{df\left({\overrightarrow{x}}_i\right)}{d{\overrightarrow{x}}_i}$vec(r)_(i)=-(df( vec(x)_(i)))/(d vec(x)_(i))\vec{r}_{i}=-\frac{d f\left(\vec{x}_{i}\right)}{d \vec{x}_{i}}${\overrightarrow{r}}_i=-\frac{df\left({\overrightarrow{x}}_i\right)}{d{\overrightarrow{x}}_i}$ and ${\overrightarrow{r}}_{i+1}=$${\overrightarrow{r}}_{i+1}=$vec(r)_(i+1)=\vec{r}_{i+1}=${\overrightarrow{r}}_{i+1}=$ $-\frac{df\left({\overrightarrow{x}}_{i+1}\right)}{d{\overrightarrow{x}}_{i+1}}$$-\frac{df\left({\overrightarrow{x}}_{i+1}\right)}{d{\overrightarrow{x}}_{i+1}}$-(df( vec(x)_(i+1)))/(d vec(x)_(i+1))-\frac{d f\left(\vec{x}_{i+1}\right)}{d \vec{x}_{i+1}}$-\frac{df\left({\overrightarrow{x}}_{i+1}\right)}{d{\overrightarrow{x}}_{i+1}}$. However, unlike the relatively "random" selection of $\alpha$$\alpha$alpha\alpha$\alpha$, CG determines the step size by searching for the lowest objective function value along this fastest descending direction. We know that the lowest objective function presents the following condition:

where ${\overrightarrow{x}}_i$${\overrightarrow{x}}_i$vec(x)_(i)\vec{x}_{i}${\overrightarrow{x}}_i$ is the state variable in the current step (or model parameters " ${\overrightarrow{\theta }}_i$${\overrightarrow{\theta }}_i$vec(theta)_(i)\vec{\theta}_{i}${\overrightarrow{\theta }}_i$ " in the current optimization step) and thus ${\overrightarrow{x}}_{i+1}$${\overrightarrow{x}}_{i+1}$vec(x)_(i+1)\vec{x}_{i+1}${\overrightarrow{x}}_{i+1}$ is the optimization state (model) that we will reach if we move along the fastest descending direction.

The following step is the key. We reformulate the above equation using the chain rule.

In the remaining deduction, we will use a quadratic optimization problem, which will minimize the following function if $\overline{A}$$\overline{A}$bar(A)\bar{A}$\overline{A}$ is positive definite: $f(\overrightarrow{x})=\frac{1}{2}{\overrightarrow{x}}^T\cdot \overrightarrow{A}\cdot \overrightarrow{x}-{\overrightarrow{b}}^T\cdot \overrightarrow{x}+c$$f(\overrightarrow{x})=\frac{1}{2}{\overrightarrow{x}}^T\cdot \overrightarrow{A}\cdot \overrightarrow{x}-{\overrightarrow{b}}^T\cdot \overrightarrow{x}+c$f( vec(x))=(1)/(2) vec(x)^(T)* vec(A)* vec(x)- vec(b)^(T)* vec(x)+cf(\vec{x})=\frac{1}{2} \vec{x}^{T} \cdot \vec{A} \cdot \vec{x}-\vec{b}^{T} \cdot \vec{x}+c$f(\overrightarrow{x})=\frac{1}{2}{\overrightarrow{x}}^T\cdot \overrightarrow{A}\cdot \overrightarrow{x}-{\overrightarrow{b}}^T\cdot \overrightarrow{x}+c$.

It is noted the optimization problem is equivalent to the solution to the linear function: ${\overline{A}}^T\cdot \overrightarrow{x}=\overrightarrow{b}$${\overline{A}}^T\cdot \overrightarrow{x}=\overrightarrow{b}$bar(A)^(T)* vec(x)= vec(b)\bar{A}^{T} \cdot \vec{x}=\vec{b}${\overline{A}}^T\cdot \overrightarrow{x}=\overrightarrow{b}$.
Next, let us take a look at two basic parameters defined for this quadratic problem.
Error:

Residual: ${\overline{A}}^T\cdot {\overrightarrow{x}}_i\ne \overrightarrow{b}$${\overline{A}}^T\cdot {\overrightarrow{x}}_i\ne \overrightarrow{b}$bar(A)^(T)* vec(x)_(i)!= vec(b)\bar{A}^{T} \cdot \vec{x}_{i} \neq \vec{b}${\overline{A}}^T\cdot {\overrightarrow{x}}_i\ne \overrightarrow{b}$ because ${\overrightarrow{x}}_i\ne \overrightarrow{x}$${\overrightarrow{x}}_i\ne \overrightarrow{x}$vec(x)_(i)!= vec(x)\vec{x}_{i} \neq \vec{x}${\overrightarrow{x}}_i\ne \overrightarrow{x}$

We can derive

The above equation shows the relationship between ${\overrightarrow{r}}_i$${\overrightarrow{r}}_i$vec(r)_(i)\vec{r}_{i}${\overrightarrow{r}}_i$ and ${\overrightarrow{e}}_i$${\overrightarrow{e}}_i$vec(e)_(i)\vec{e}_{i}${\overrightarrow{e}}_i$, which is very useful for us to understand the problem. However, we use $-\frac{df\left({\overrightarrow{x}}_i\right)}{d{\overrightarrow{x}}_i}$$-\frac{df\left({\overrightarrow{x}}_i\right)}{d{\overrightarrow{x}}_i}$-(df( vec(x)_(i)))/(d vec(x)_(i))-\frac{d f\left(\vec{x}_{i}\right)}{d \vec{x}_{i}}$-\frac{df\left({\overrightarrow{x}}_i\right)}{d{\overrightarrow{x}}_i}$ to calculate ${\overrightarrow{r}}_i$${\overrightarrow{r}}_i$vec(r)_(i)\vec{r}_{i}${\overrightarrow{r}}_i$, because ${\overrightarrow{e}}_i$${\overrightarrow{e}}_i$vec(e)_(i)\vec{e}_{i}${\overrightarrow{e}}_i$ cannot be calculated as the true optimal point ${\overrightarrow{x}}_i$${\overrightarrow{x}}_i$vec(x)_(i)\vec{x}_{i}${\overrightarrow{x}}_i$ is unknown.

Next, let us show how to derive the formulation for calculating $\alpha$$\alpha$alpha\alpha$\alpha$ :

Then, we can obtain the following equation for calculating ${\alpha }_i$${\alpha }_i$alpha_(i)\alpha_{i}${\alpha }_i$ :

CG can be implemented with different iterative procedures, leading to different CG variations. One intuitive way is to use the following three equations:

Alternatively, we can multiply (dot product) the two sides of Eq. 17.106 by $-\overline{A}$$-\overline{A}$- bar(A)-\bar{A}$-\overline{A}$ and use the relationship ${\overrightarrow{r}}_i=-\overline{A}({\overrightarrow{x}}_i-$${\overrightarrow{r}}_i=-\overline{A}\left({\overrightarrow{x}}_i-\right.$vec(r)_(i)=- bar(A)( vec(x)_(i)-:}\vec{r}_{i}=-\bar{A}\left(\vec{x}_{i}-\right.${\overrightarrow{r}}_i=-\overline{A}({\overrightarrow{x}}_i-$ $\overrightarrow{x})$$\overrightarrow{x})$vec(x))\vec{x})$\overrightarrow{x})$, yielding

This can be used with Eq. 17.105 for the update. However, it is worthwhile to mention that this would involve more numerical errors. The use of ${\overrightarrow{x}}_i$${\overrightarrow{x}}_i$vec(x)_(i)\vec{x}_{i}${\overrightarrow{x}}_i$ for calculating ${\overrightarrow{r}}_i$${\overrightarrow{r}}_i$vec(r)_(i)\vec{r}_{i}${\overrightarrow{r}}_i$ frequently can help alleviate this issue.

The above deduction was presented based on a quadratic program problem (or linear equation solution). Notwithstanding, CG has been extended for handling nonlinear problems such as Fletcher-Reeves method, Hestenes-Stiefel method, and Dai-Yuan method [176]. However, it is noted that CG has rarely been used for large-scale deep-learning problems. The nonlinear versions of CG require a line search to identify the lowest point along the direction of the fastest descent. This could cause difficulty in applying CG to nonlinear problems, such as additional computational effort, but this may
not be the primary reason. One major concern lies in the use of batches for line search. The use of the whole batch can lead to high computing demands but, importantly, force the optimizer to converge to the nearest local minimum, which is not desired. Notwithstanding, such issues may be addressed in the future. Thus, CG is still introduced here considering its potential.

As mentioned above, the Expectation Maximization (EM) methods have a much broader definition. Due to the same reason, it is hard to define a general approximate function for them like what we did for gradient-based and Newton's methods. Also, the formulation and implementation of this type of method can be much different, depending on the applications and algorithms. Thus, the introduction to EM in this subsection will be divided into two parts. First, we will play with the math underneath one typical example to show what an approximate function could look like. Next, we will go through one simple example to get a more intuitive understanding and first-hand experience about the implementation of the basic EM method.

First, to peek into the approximate function, let us use cross entropy to construct the objective function to set up an example.

where $x$$x$xx$x$ and $y$$y$yy$y$ are two state variables, $p$$p$pp$p$ is the probability, and $\tilde{p}$$\tilde{p}$tilde(p)\tilde{p}$\tilde{p}$ is the prediction of $p$$p$pp$p$.
In a typical classification problem, let us use $z$$z$zz$z$ to represent the class and then apply the chain rule. We can obtain

$p(y)$$p(y)$p(y)p(y)$p(y)$ is a fixed number. So, the above objective function can be modified by removing this term. So, we have

The following gradients can be obtained:

The application of gradient-based methods in this case is not easy because of extra constraints: $\sum _{x}p(x\mid z)=1$$\sum _x p(x\mid z)=1$sum_(x)p(x∣z)=1\sum_{x} p(x \mid z)=1$\sum _{x}p(x\mid z)=1$, $\sum _{y}p(z\mid y)=1,p(x\mid z)⩾0$$\sum _y p(z\mid y)=1,p(x\mid z)⩾0$sum_(y)p(z∣y)=1,p(x∣z) >= 0\sum_{y} p(z \mid y)=1, p(x \mid z) \geqslant 0$\sum _{y}p(z\mid y)=1,p(x\mid z)⩾0$, and $p(z\mid y)⩾0$$p(z\mid y)⩾0$p(z∣y) >= 0p(z \mid y) \geqslant 0$p(z\mid y)⩾0$. The position of log in the above loss function causes difficulty. Thus, we can introduce the following approximate function:

The gradients of this appropriate objective function are

Comparing the gradients of this approximate function with those of the original function, e.g., $\mathrm{\nabla }\ell$$\mathrm{\nabla }\ell$gradℓ\nabla \ell$\mathrm{\nabla }\ell$ vs $\mathrm{\nabla }g$$\mathrm{\nabla }g$grad g\nabla g$\mathrm{\nabla }g$, it is not difficult to obtain

Substituting the above equation into the $g$$g$gg$g$ function will generate an approximate function for this specific example. As can be seen, this is much different from those in the gradient-based methods and Newton's method. Other approximate functions can be derived for other EM applications.

The above deduction is provided to show the similarity between EM and other optimization methods. However, implementations of EM do not need the above deduction and are different from the previous optimization methods. The key to most EM implementations is to construct and/or utilize hidden parameters. An iterative process involving alternately updating the major optimization parameters and the hidden parameters will lead to the optimal parameters and the model they define. Taking the above deduction as an example, we first can calculate $C_{x,y,z}$$C_{x,y,z}$C_(x,y,z)C_{x, y, z}$C_{x,y,z}$ using $p(x\mid z)$$p(x\mid z)$p(x∣z)p(x \mid z)$p(x\mid z)$ and $p(z\mid y)$$p(z\mid y)$p(z∣y)p(z \mid y)$p(z\mid y)$. Then $C_{x,y,z}$$C_{x,y,z}$C_(x,y,z)C_{x, y, z}$C_{x,y,z}$ can be used to compute $p(x\mid z)$$p(x\mid z)$p(x∣z)p(x \mid z)$p(x\mid z)$ and $p(z\mid y)$$p(z\mid y)$p(z∣y)p(z \mid y)$p(z\mid y)$.

The above deduction is performed based on a meaningful yet abstract example. To gain a more intuitive understanding, let us consider one real-world example that is easy to understand.

In this example, we tossed two coins. Each time we tossed one coin and recorded the number of times that the two sides of each coin appeared, i.e., heads and tails. Now, we will show how to compute the expected probabilities of getting the sides for each coin and guess which coin was used each time.

Table 17.1: Results of coin toss

Table 17.1 shows the results of the test. Please be aware that which coin was selected for each round of toss is unknown when solving the problem. However, this fact is recorded in the above table for validation purposes.

This problem can be solved using EM. The key is to identify a hidden parameter(s). Before that, we need to figure out the model to be sought, or in other words, the parameters to be optimized. These parameters can be the probabilities of getting the two sides for each coin. Let us use $P_A$$P_A$P_(A)P_{A}$P_A$ and $P_B$$P_B$P_(B)P_{B}$P_B$ to represent the probabilities of obtaining the heads for the two coins. Accordingly, the probabilities for getting the tail side for the two coins are $1-P_A$$1-P_A$1-P_(A)1-P_{A}$1-P_A$ and $1-P_B$$1-P_B$1-P_(B)1-P_{B}$1-P_B$. In the above problem description, we know there are other unknown parameters, that is, "which coin was tossed" in each of the five rounds. Intuitively, we can consider using these unknowns as the hidden parameters. Let us use $[{\theta }_1,{\theta }_2,{\theta }_3,{\theta }_4,{\theta }_5]$$\left[{\theta }_1,{\theta }_2,{\theta }_3,{\theta }_4,{\theta }_5\right]$[theta_(1),theta_(2),theta_(3),theta_(4),theta_(5)]\left[\theta_{1}, \theta_{2}, \theta_{3}, \theta_{4}, \theta_{5}\right]$[{\theta }_1,{\theta }_2,{\theta }_3,{\theta }_4,{\theta }_5]$ to represent them, e.g., ${\theta }_1$${\theta }_1$theta_(1)\theta_{1}${\theta }_1$ is the probability of selecting Coin A in the first round, and likewise, $1-{\theta }_1$$1-{\theta }_1$1-theta_(1)1-\theta_{1}$1-{\theta }_1$ is the probability of selecting Coin B in the first round.

Let us start with random values $P_A=0.6$$P_A=0.6$P_(A)=0.6P_{A}=0.6$P_A=0.6$ and $P_B=0.5$$P_B=0.5$P_(B)=0.5P_{B}=0.5$P_B=0.5$ for initialization. Iteration 1: ${\theta }_1=0.6,P_B=0.5$${\theta }_1=0.6,P_B=0.5$theta_(1)=0.6,P_(B)=0.5\theta_{1}=0.6, P_{B}=0.5${\theta }_1=0.6,P_B=0.5$

Round 1: $P_A=\frac{{0.6}^5\cdot {0.4}^5}{{0.6}^5\cdot {0.4}^5+{0.5}^5\cdot {0.5}^5}=0.45$$P_A=\frac{{0.6}^5\cdot {0.4}^5}{{0.6}^5\cdot {0.4}^5+{0.5}^5\cdot {0.5}^5}=0.45$P_(A)=(0.6^(5)*0.4^(5))/(0.6^(5)*0.4^(5)+0.5^(5)*0.5^(5))=0.45P_{A}=\frac{0.6^{5} \cdot 0.4^{5}}{0.6^{5} \cdot 0.4^{5}+0.5^{5} \cdot 0.5^{5}}=0.45$P_A=\frac{{0.6}^5\cdot {0.4}^5}{{0.6}^5\cdot {0.4}^5+{0.5}^5\cdot {0.5}^5}=0.45$
for Coin A, we have the following numbers of times to get heads and tails: $5\ast 0.45=2.2,5\ast 0.45=2.2$$5\ast 0.45=2.2,5\ast 0.45=2.2$5**0.45=2.2,5**0.45=2.25 * 0.45=2.2,5 * 0.45=2.2$5\ast 0.45=2.2,5\ast 0.45=2.2$
for Coin B , we have the following numbers of times to get heads and tails: $5\ast (1-0.45)=2.8,5\ast (1-0.45)=2.8$$5\ast (1-0.45)=2.8,5\ast (1-0.45)=2.8$5**(1-0.45)=2.8,5**(1-0.45)=2.85 *(1-0.45)=2.8,5 *(1-0.45)=2.8$5\ast (1-0.45)=2.8,5\ast (1-0.45)=2.8$
Round 2: $P_A=\frac{{0.6}^9\cdot {0.4}^1}{{0.6}^9\cdot {0.4}^1+{0.5}^9\cdot {0.5}^1}=0.8$$P_A=\frac{{0.6}^9\cdot {0.4}^1}{{0.6}^9\cdot {0.4}^1+{0.5}^9\cdot {0.5}^1}=0.8$P_(A)=(0.6^(9)*0.4^(1))/(0.6^(9)*0.4^(1)+0.5^(9)*0.5^(1))=0.8P_{A}=\frac{0.6^{9} \cdot 0.4^{1}}{0.6^{9} \cdot 0.4^{1}+0.5^{9} \cdot 0.5^{1}}=0.8$P_A=\frac{{0.6}^9\cdot {0.4}^1}{{0.6}^9\cdot {0.4}^1+{0.5}^9\cdot {0.5}^1}=0.8$
for Coin A , we have the following numbers of times to get heads and tails: $9\ast 0.8=7.2,1\ast 0.8=0.8$$9\ast 0.8=7.2,1\ast 0.8=0.8$9**0.8=7.2,1**0.8=0.89 * 0.8=7.2,1 * 0.8=0.8$9\ast 0.8=7.2,1\ast 0.8=0.8$
for Coin $B$$B$BB$B$, we have the following numbers of times to get heads and tails: $9\ast (1-0.8)=1.8,1\ast (1-0.8)=0.2$$9\ast (1-0.8)=1.8,1\ast (1-0.8)=0.2$9**(1-0.8)=1.8,1**(1-0.8)=0.29 *(1-0.8)=1.8,1 *(1-0.8)=0.2$9\ast (1-0.8)=1.8,1\ast (1-0.8)=0.2$
Finishing all the five rounds for the first iteration, as shown in Table 17.2, we would get 21.3 heads and 8.6 tails for Coin A and 11.7 heads and 8.4 tails for Coin B. Then we can use the following two equations to update $P_A$$P_A$P_(A)P_{A}$P_A$ and $P_B$$P_B$P_(B)P_{B}$P_B$, which are needed for the next iteration.